class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
		vector<vector<int>> ret;
		sort(nums.begin(),nums.end());
		int a=0,n=nums.size();
		while(a<n)
		{
			int b=a+1;
			while(b<n)
			{
				int left=b+1,right=n-1;
				long long aim=(long long)target-nums[a]-nums[b];
				while(left<right)
				{
					int sum=nums[left]+nums[right];
					if(sum<aim)
					{
						left++;
					}
					else if(sum>aim)
					{
						right--;
					}
					else
					{
						ret.push_back({nums[a],nums[b],nums[left++],nums[right--]});
						while(left<right&&nums[left]==nums[left-1])
						{
							left++;
						}
						while(left<right&&nums[right]==nums[right+1])
						{
							right--;
						}
					}

				}
				b++;
				while(b<n&&nums[b]==nums[b-1])
				{
					b++;
				}
			}
			a++;
			while(a<n&&nums[a]==nums[a-1])
			{
				a++;
			}
		}
		return ret;
    }
};
